Q1. binary tree 是什麼

• 二元樹 (binary tree) 是一種資料結構，應用非常廣泛，是資訊人必學的基礎概念
• 二元樹是圖論中的一種樹，這種樹中的每一個節點，最多只能分支出兩個子節點。
  • 當然，也有二元樹、三元樹等，可將此概念推廣為 N-ary Tree，表示最多分支出 N 個節點的樹。
• 二元樹的優勢是，容易實作，能快速找到任意節點的 parent 跟 child，可以利用二元樹的概念建構出二元搜尋樹 (Binary Search Tree)，能夠有效進行插入、搜尋
• 二元樹的架構/術語

  • 二元樹的架構

    • 節點 (node)：圖中的點
      

      • 根節點 (root)：最上層的節點，也是整棵樹第一個節點、唯一沒有父節點的節點。
        

      • 葉節點 (leaf)：最下層的節點，也就是沒有子節點的節點
        

      • 父節點 (parent) 與 子節點 (child)：一個節點可以繼續往下層長出其他節點，此時對長出來的節點稱為子節點，而子節點的上層節點稱為父節點。

        • 在二元樹中，一個 parent 只會有 0 ~ 2 個 child，而每個 child 只會有一個 parent
        • 在 Tree 的概念 (非二元樹) 中，一個 parent 底下的 child 數目沒有限制
        • Binary Tree 可以推廣為 N-ary Tree，表示一個 parent 只會有不超過 N 個 child 的 tree。
          

      • 手足 (sibling)：同一個父親底下的 child，他兩個互為 sibling

      

    • 分支 (branch)：圖中的邊
      

  • 節點深度：一個節點位於這棵樹的第幾層 (level) 就稱為該節點的深度，或者說，從該節點到 root 途經的 edge 數量即為節點深度。

  • 樹的高度/深度：一顆樹目前最高長到第幾層，就稱為該樹的高度，又或者說，離根節點最遠的葉節點深度即為該樹的高度。

• 二元樹種類

  • 完滿二元樹 (full binary tree) ：除了 leaf 之外的所有節點，都有填滿兩個 child
    

  • 完整二元樹 (complete binary tree)：除了最後一層，其他層的節點全部填滿，並且最後一層必須是從左向右填，中間沒有空缺。
    

  • perfect binary tree：每一層節點都滿的，同時滿足 full 和 complete。
    

  • 歪斜樹 (Skewed Binary Tree)

    • 左歪斜樹：一顆樹完全都往左邊長，沒有任何 right child。
      

    • 右歪斜樹：一顆樹完全都往右邊長，沒有任何 left chil
      

參考資料：https://web.ntnu.edu.tw/~algo/BinaryTree.html

參考資料：https://zh.wikipedia.org/wiki/二叉树

參考資料：https://www.geeksforgeeks.org/binary-tree-set-3-types-of-binary-tree/

Q2. 學會 binary tree概念可以做什麼 ?

• 二元搜尋樹 (Binary Search Tree) 是使用 binary tree 的結構達成
  • 改進版的二元搜尋樹：AVL樹、紅黑樹

Lab. 明天要解的題目：94. Binary Tree Inorder Traversal

• 題目連結：https://leetcode.com/problems/binary-tree-inorder-traversal/

• 題目敘述：

  • 題目會給一個二元樹結構的資料
    

• 測資的 Input/Output

  • 會給一個指向 root 的資料
  • 回傳中序排列
    

• 題目的條件

  • tree 的 node 數量為 0~100 之間
  • 每個 node 的值於 -100~100 之間